package com.jia.explore.dynamicprogramming.knapsack;

import java.util.Scanner;

/**
 * @program: Leetcode
 * @description: 多重背包 https://www.acwing.com/problem/content/4/
 * @author: STU756
 * @create: 2020-08-11 12:50
 */
public class Dy_MultipleBackpack {public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = 110;
    int[] v = new int[N];
    int[] w = new int[N];
    int[] c = new int[N];
    int n = scanner.nextInt();
    int m = scanner.nextInt();
    int count = 1;
    while(count <= n) {
        v[count] = scanner.nextInt();
        w[count] = scanner.nextInt();
        c[count] = scanner.nextInt();
        ++count;
    }
    /**
     * 01背包拓展
     * f[j]表示空间为j的最大价值
     * for(int i = 1; i <=n; i++){
     *  for(int j = m; j >= v[i]; j--){
     *      f[j] = max(f[j], f[j - v[i]] + w[i], f[j-2*v[i]] + w[i], ....)
     *  }
     * }
     */
    int[] f = new int[N];
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= v[i]; j--) {
            //有c[i]个
            for(int k = 1; k <= c[i] && k * v[i] <= j; k++) {
                f[j] = Math.max(f[j], f[j - k * v[i]] + k * w[i]);
            }
        }
    }
    System.out.println(f[m]);
}

}
